11459. Существование пропуска

Задана последовательность из n чисел: A = (a₁, a₂, ..., a_n).

Определить, существует ли пара (i, j) с 1 ≤ i, j ≤ n такая, что a_i – a_j = x.

Вход. Первая строка содержит два числа n (2 ≤ n ≤ 2 ⋅ 10⁵) и x (-10⁹ ≤ x ≤ 10⁹).

Вторая строка содержит n целых чисел a₁, a₂, ..., a_n (-10⁹ ≤ a_i ≤ 10⁹).

Выход. Выведите Yes, если существует пара (i, j) с 1 ≤ i, j ≤ n такая, что a_i – a_j = x, и No в противном случае.

Пример входа 1	Пример выхода 1
7 3 2 8 7 6 1 12 5	Yes
Пример входа 2	Пример выхода 2
7 3 2 8 7 1 12 6 1	No

РЕШЕНИЕ

структуры данных – set

Анализ алгоритма

Перепишем равенство в виде: a_i = a_j + x.

Занесем заданную последоватлеьность во множество s. Далее для каждого элемента a из множества проверим, лежит ли во множестве число a + x. Если ответ положительный, то выводим Yes. Если ни для какого элемента a из множества число a + x не принадлежит множеству, то выводим No.

Пример

Рассмотрим первый пример. Занесем все числа во множество.

Имеется пара чисел (5, 8), разность между которыми равна x = 3.

Реализация алгоритма

Читаем входные данные. Заносим последоватлеьность во множество s.

scanf("%d %d", &n, &x);

for (i = 0; i < n; i++)

{

scanf("%d", &a);

s.insert(a);

}

Для каждого элемента a из множества s проверяем, принадлежит ли множеству число a + x.

for (int a : s)

{

if (s.find(a + x) != s.end())

{

Если число a + x принадлежит множеству, то выводим Yes и останавливаем работу программы.

printf("Yes\n");

return 0;

}

}

Если сообщение Yes не было выведено, то выводим No.

printf("No\n");